package com.shm.leetcode;

import java.util.Deque;
import java.util.LinkedList;
import java.util.TreeMap;

/**
 * 456. 132模式
 * 给你一个整数数组 nums ，数组中共有 n 个整数。132 模式的子序列 由三个整数 nums[i]、nums[j] 和 nums[k] 组成，并同时满足：i < j < k 和 nums[i] < nums[k] < nums[j] 。
 *
 * 如果 nums 中存在 132 模式的子序列 ，返回 true ；否则，返回 false 。
 *
 *
 *
 * 进阶：很容易想到时间复杂度为 O(n^2) 的解决方案，你可以设计一个时间复杂度为 O(n logn) 或 O(n) 的解决方案吗？
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,3,4]
 * 输出：false
 * 解释：序列中不存在 132 模式的子序列。
 * 示例 2：
 *
 * 输入：nums = [3,1,4,2]
 * 输出：true
 * 解释：序列中有 1 个 132 模式的子序列： [1, 4, 2] 。
 * 示例 3：
 *
 * 输入：nums = [-1,3,2,0]
 * 输出：true
 * 解释：序列中有 3 个 132 模式的的子序列：[-1, 3, 2]、[-1, 3, 0] 和 [-1, 2, 0] 。
 *
 *
 * 提示：
 *
 * n == nums.length
 * 1 <= n <= 104
 * -109 <= nums[i] <= 109
 * @author SHM
 */
public class Find132pattern {
    /**
     * 前言
     * 由于本题中 nn 的最大值可以到 1500015000，因此对于一个满足 132132 模式的三元组下标 (i, j, k)(i,j,k)，枚举其中的 22 个下标时间复杂度为 O(n^2)O(n
     * 2
     *  )，很容易超出时间限制。
     *
     * 因此我们可以考虑枚举其中的 11 个下标，并使用合适的数据结构维护另外的 22 个下标的可能值。
     *
     * 方法一：枚举 33
     * 思路与算法
     *
     * 枚举 33 是容易想到并且也是最容易实现的。由于 33 是模式中的最大值，并且其出现在 11 和 22 的中间，因此我们只需要从左到右枚举 33 的下标 jj，那么：
     *
     * 由于 11 是模式中的最小值，因此我们在枚举 jj 的同时，维护数组 aa 中左侧元素 a[0..j-1]a[0..j−1] 的最小值，即为 11 对应的元素 a[i]a[i]。需要注意的是，只有 a[i] < a[j]a[i]<a[j] 时，a[i]a[i] 才能作为 11 对应的元素；
     *
     * 由于 22 是模式中的次小值，因此我们可以使用一个有序集合（例如平衡树）维护数组 aa 中右侧元素 a[j+1..n-1]a[j+1..n−1] 中的所有值。当我们确定了 a[i]a[i] 和 a[j]a[j] 之后，只需要在有序集合中查询严格比 a[i]a[i] 大的那个最小的元素，即为 a[k]a[k]。需要注意的是，只有 a[k] < a[j]a[k]<a[j] 时，a[k]a[k] 才能作为 33 对应的元素。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(n \log n)O(nlogn)。在初始化时，我们需要 O(n \log n)O(nlogn) 的时间将数组元素 a[2..n-1]a[2..n−1] 加入有序集合中。在枚举 jj 时，维护左侧元素最小值的时间复杂度为 O(1)O(1)，将 a[j+1]a[j+1] 从有序集合中删除的时间复杂度为 O(\log n)O(logn)，总共需要枚举的次数为 O(n)O(n)，因此总时间复杂度为 O(n \log n)O(nlogn)。
     *
     * 空间复杂度：O(n)O(n)，即为有序集合存储右侧所有元素需要使用的空间。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/132-pattern/solution/132mo-shi-by-leetcode-solution-ye89/
     * @param nums
     * @return
     */
    public boolean find132pattern(int[] nums) {
        int leftMin = nums[0];
        TreeMap<Integer,Integer> rightAll = new TreeMap<>();
        for (int i = 2; i < nums.length; i++) {
            rightAll.put(nums[i],rightAll.getOrDefault(nums[i],0)+1);
        }
        for (int j = 1; j < nums.length-1; j++) {
            Integer next = rightAll.ceilingKey(leftMin+1);
            if (next!=null&&next<nums[j]){
                return true;
            }
            leftMin = Math.min(leftMin,nums[j]);
            rightAll.put(nums[j+1],rightAll.get(nums[j+1])-1);
            if(rightAll.get(nums[j+1])==0){
                rightAll.remove(nums[j+1]);
            }
        }
        return false;
    }


    /**
     * 方法二：枚举 11
     * 思路与算法
     *
     * 如果我们从左到右枚举 11 的下标 ii，那么 j, kj,k 的下标范围都是减少的，这样就不利于对它们进行维护。因此我们可以考虑从右到左枚举 ii。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/132-pattern/solution/132mo-shi-by-leetcode-solution-ye89/
     *
     * 使用单调栈维护 3
     * 如果我们维护的是 132 模式中的 3，那么就希望 1 尽可能小，2 尽可能大。
     *
     * 所以思路是这样的：
     *
     * 遍历的位置 j 相当于 132 模式中的 3，即 nums[j] ；
     * 找到 3 左边的最小元素 为 1，即 nums[i] ；
     * 找到 3 右边的比 3 小的最大元素 为 2，即 nums[k] ；
     * 在方法一的做法中，是使用暴力求解得到的 2，很显然时间复杂度比较高。我们想要的 2 其实满足两个条件：
     *
     * 比 3 小；
     * 在 nums[j+1 .. N-1]nums[j+1..N−1] 区间的最大元素。
     * 为了找到这样的元素，我们可以使用一个单调递减的「栈」。所谓「单调栈」就是栈中的元素都是依次递增或者递减的，从而方便我们能维护好数组的一个区间内的「最大值」「次大值」等等。
     *
     * 想要求比 3 小的最大元素，则需要一个单调递减的栈。这样的话，最大元素在栈底，次大元素在栈底的第二元素……
     *
     * 具体到本题的实现方式：
     *
     * 求任何位置的左边最小的元素 nums[i] ，可以提前遍历一次而得到；
     * 使用「单调递减栈」，把 nums[j]  入栈时，需要把栈里面比它小的元素全都 pop 出来，由于越往栈底越大，所以 pop 出的最后一个元素，就是比 3 小的最大元素 nums[k] 。
     * 判断如果 nums[i] < nums[k] ，那就说明得到了一个 132 模式。
     * 因为单调栈是建立在 3 的右边的，因此，我们使用从右向左遍历。
     *
     * 时间复杂度：O(N)O(N)
     * 空间复杂度：O(N)O(N)
     * 作者：fuxuemingzhu
     * 链接：https://leetcode-cn.com/problems/132-pattern/solution/fu-xue-ming-zhu-cong-bao-li-qiu-jie-dao-eg78f/
     * @param nums
     * @return
     */
    public boolean find132pattern_2(int[] nums) {
        int n = nums.length;
        Deque<Integer> deque = new LinkedList<>();
        deque.push(nums[n-1]);
        int maxK = Integer.MIN_VALUE;
        for (int i = n - 2; i >= 0; i--) {
            if(nums[i]<maxK){
                return true;
            }
            while (!deque.isEmpty()&&nums[i]>deque.peek()){
                maxK=deque.pop();
            }
            if(nums[i]>maxK){
                deque.push(nums[i]);
            }
        }
        return false;
    }
}
